﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.Runtime.InteropServices;
using System.Threading;
using Microsoft.Goldenlight.Resources;

namespace Microsoft.Goldenlight.Collections
{
    /// <summary>
    /// 	Represents a doubly linked list.
    /// </summary>
    /// <typeparam name="T"> Specifies the element type of the linked list. </typeparam>
    [ComVisible(false)]
    [DebuggerTypeProxy(typeof (CollectionDebugView<>))]
    [DebuggerDisplay("Count = {Count}")]
    public class DoublyLinkedList<T> : ICollection<T>, ICollection
    {
        #region Fields & Properties

        private object _syncRoot;
        private int _count;

        private DoublyLinkedListNode<T> _head;

        /// <summary>
        /// 	Gets the first node of the DoublyLinkedList.
        /// </summary>
        /// <returns> The first DoublyLinkedListNode of the DoublyLinkedList. </returns>
        public DoublyLinkedListNode<T> First
        {
            get
            {
                return _head;
            }
        }

        private DoublyLinkedListNode<T> _tail;

        /// <summary>
        /// 	Gets the last node of the DoublyLinkedList.
        /// </summary>
        /// <returns> The last DoublyLinkedListNode of the DoublyLinkedList. </returns>
        public DoublyLinkedListNode<T> Last
        {
            get
            {
                return _tail;
            }
        }

        #endregion

        #region Constructors

        /// <summary>
        /// 	Initializes a new instance of the DoublyLinkedList class that is empty.
        /// </summary>
        public DoublyLinkedList()
        {
        }

        /// <summary>
        /// 	Initializes a new instance of the DoublyLinkedList class that contains elements copied from the specified <see
        ///  	cref="T:System.Collections.IEnumerable" /> and has sufficient capacity to accommodate the number of elements copied.
        /// </summary>
        /// <param name="collection"> The IEnumerable whose elements are copied to the new DoublyLinkedList. </param>
        public DoublyLinkedList(IEnumerable<T> collection)
        {
            if (collection == null)
            {
                throw new ArgumentNullException("collection");
            }
            foreach (var value in collection)
            {
                AddLast(value);
            }
        }

        #endregion

        #region Implementation of IEnumerable

        /// <summary>
        /// 	Returns an enumerator that iterates through the collection.
        /// </summary>
        /// <returns> A <see cref="T:System.Collections.Generic.IEnumerator`1" /> that can be used to iterate through the collection. </returns>
        public IEnumerator<T> GetEnumerator()
        {
            return new Enumerator(this);
        }

        /// <summary>
        /// 	Returns an enumerator that iterates through a collection.
        /// </summary>
        /// <returns> An <see cref="T:System.Collections.IEnumerator" /> object that can be used to iterate through the collection. </returns>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        #region Implementation of ICollection<T>

        /// <summary>
        /// 	Adds an value to the ICollection .
        /// </summary>
        /// <param name="value"> The object to add to the ICollection . </param>
        void ICollection<T>.Add(T value)
        {
            AddLast(value);
        }

        /// <summary>
        /// 	Removes all items from the ICollection .
        /// </summary>
        public void Clear()
        {
            var current = _head;
            while (current != null)
            {
                var node = current;
                current = current.Next;
                DoublyLinkedListNode<T>.Free(node);
            }
            _head = null;
            _tail = null;
            _count = 0;
        }

        /// <summary>
        /// 	Determines whether the ICollection contains a specific value.
        /// </summary>
        /// <returns> true if value is found in the ICollection ; otherwise, false. </returns>
        /// <param name="value"> The object to locate in the ICollection . </param>
        public bool Contains(T value)
        {
            return Find(value) != null;
        }

        /// <summary>
        /// 	Copies the entire DoublyLinkedList to a compatible one-dimensional Array, starting at the specified index of the target array.
        /// </summary>
        /// <param name="array"> The one-dimensional Array that is the destination of the elements copied from DoublyLinkedList. The Array must have zero-based indexing. </param>
        /// <param name="index"> The zero-based index in array at which copying begins. </param>
        public void CopyTo(T[] array, int index)
        {
            if (array == null)
            {
                throw new ArgumentNullException("array");
            }
            if (index < 0 || index > array.Length)
            {
                throw new ArgumentOutOfRangeException("index", string.Format(CultureInfo.CurrentCulture, Resx.ArrayIndexOutOfRange, index));
            }
            if ((array.Length - index) < Count)
            {
                throw new ArgumentException(Resx.ArrayInsufficientSpace);
            }
            var current = _head;
            while (current != null)
            {
                array[index++] = current.Value;
                current = current.Next;
            }
        }

        /// <summary>
        /// 	Removes the first occurrence of the specified value from the DoublyLinkedList.
        /// </summary>
        /// <param name="value"> The value to remove from the DoublyLinkedList. </param>
        /// <returns> true if the element containing value is successfully removed; otherwise, false. This method also returns false if value was not found in the original DoublyLinkedList. </returns>
        public bool Remove(T value)
        {
            var node = Find(value);
            if (node != null)
            {
                InternalRemoveNode(node);
                return true;
            }
            return false;
        }

        /// <summary>
        /// 	Gets the number of nodes actually contained in the DoublyLinkedList.
        /// </summary>
        /// <returns> The number of nodes actually contained in the DoublyLinkedList. </returns>
        public int Count
        {
            get
            {
                return _count;
            }
        }

        /// <summary>
        /// 	Gets a value indicating whether the ICollection is read-only.
        /// </summary>
        /// <returns> true if the ICollection is read-only; otherwise, false. </returns>
        bool ICollection<T>.IsReadOnly
        {
            get
            {
                return false;
            }
        }

        #endregion

        #region Implementation of ICollection

        /// <summary>
        /// 	Copies the elements of the ICollection to an Array, starting at a particular Array index.
        /// </summary>
        /// <param name="array"> The one-dimensional Array that is the destination of the elements copied from ICollection. The Array must have zero-based indexing. </param>
        /// <param name="index"> The zero-based index in array at which copying begins. </param>
        void ICollection.CopyTo(Array array, int index)
        {
            if (array == null)
            {
                throw new ArgumentNullException("array");
            }
            if (array.Rank != 1)
            {
                throw new ArgumentException(Resx.ArrayMultiRank);
            }
            if (array.GetLowerBound(0) != 0)
            {
                throw new ArgumentException(Resx.ArratNonZeroLowerBound);
            }
            if (index < 0)
            {
                throw new ArgumentOutOfRangeException("index", string.Format(CultureInfo.CurrentCulture, Resx.ArrayIndexOutOfRange, index));
            }
            if ((array.Length - index) < Count)
            {
                throw new ArgumentException(Resx.ArrayInsufficientSpace);
            }
            var itemArray = array as T[];
            if (itemArray != null)
            {
                CopyTo(itemArray, index);
            }
            else
            {
                var elementType = array.GetType().GetElementType();
                var itemType = typeof (T);
                if (!elementType.IsAssignableFrom(itemType) && !itemType.IsAssignableFrom(elementType))
                {
                    throw new ArgumentException(Resx.ArrayInvalidType);
                }
                var objArray = array as object[];
                if (objArray == null)
                {
                    throw new ArgumentException(Resx.ArrayInvalidType);
                }
                var current = _head;
                try
                {
                    while (current != null)
                    {
                        objArray[index++] = current.Value;
                        current = current.Next;
                    }
                }
                catch (ArrayTypeMismatchException)
                {
                    throw new ArgumentException(Resx.ArrayInvalidType);
                }
            }
        }

        /// <summary>
        /// 	Gets an object that can be used to synchronize access to the ICollection .
        /// </summary>
        /// <returns> An object that can be used to synchronize access to the ICollection . </returns>
        object ICollection.SyncRoot
        {
            get
            {
                if (_syncRoot == null)
                {
                    Interlocked.CompareExchange<object>(ref _syncRoot, new object(), null);
                }
                return _syncRoot;
            }
        }

        /// <summary>
        /// 	Gets a value indicating whether access to the ICollection is synchronized (thread safe).
        /// </summary>
        /// <returns> true if access to the ICollection is synchronized (thread safe); otherwise, false. </returns>
        bool ICollection.IsSynchronized
        {
            get
            {
                return false;
            }
        }

        #endregion

        #region Find

        /// <summary>
        /// 	Finds the first node that contains the specified value.
        /// </summary>
        /// <returns> The first DoublyLinkedListNode that contains the specified value, if found; otherwise, null. </returns>
        /// <param name="value"> The value to locate in the DoublyLinkedList. </param>
        public DoublyLinkedListNode<T> Find(T value)
        {
            var comparer = EqualityComparer<T>.Default;
            var current = _head;
            if (value == null)
            {
                while (current != null)
                {
                    if (current.Value == null)
                    {
                        return current;
                    }
                    current = current.Next;
                }
            }
            else
            {
                while (current != null)
                {
                    if (comparer.Equals(current.Value, value))
                    {
                        return current;
                    }
                    current = current.Next;
                }
            }
            return null;
        }

        /// <summary>
        /// 	Finds the last node that contains the specified value.
        /// </summary>
        /// <returns> The last DoublyLinkedListNode that contains the specified value, if found; otherwise, null. </returns>
        /// <param name="value"> The value to locate in the DoublyLinkedList. </param>
        public DoublyLinkedListNode<T> FindLast(T value)
        {
            var comparer = EqualityComparer<T>.Default;
            var current = _tail;
            if (value == null)
            {
                while (current != null)
                {
                    if (current.Value == null)
                    {
                        return current;
                    }
                    current = current.Previous;
                }
            }
            else
            {
                while (current != null)
                {
                    if (comparer.Equals(current.Value, value))
                    {
                        return current;
                    }
                    current = current.Previous;
                }
            }
            return null;
        }

        #endregion

        #region Add

        #region Add Value

        /// <summary>
        /// 	Adds a new newNode containing the specified value at the start of the DoublyLinkedList.
        /// </summary>
        /// <returns> The new DoublyLinkedListNode containing value . </returns>
        /// <param name="value"> The value to add at the start of the DoublyLinkedList. </param>
        public DoublyLinkedListNode<T> AddFirst(T value)
        {
            var newNode = DoublyLinkedListNode<T>.Allocate(this, value);
            if (_head == null)
            {
                InternalInsertNodeToEmptyList(newNode);
                return newNode;
            }
            InternalInsertNodeBefore(_head, newNode);
            return newNode;
        }

        /// <summary>
        /// 	Adds a new newNode containing the specified value at the end of the DoublyLinkedList.
        /// </summary>
        /// <returns> The new DoublyLinkedListNode containing value. </returns>
        /// <param name="value"> The value to add at the end of the DoublyLinkedList. </param>
        public DoublyLinkedListNode<T> AddLast(T value)
        {
            var newNode = DoublyLinkedListNode<T>.Allocate(this, value);
            if (_tail == null)
            {
                InternalInsertNodeToEmptyList(newNode);
                return newNode;
            }
            InternalInsertNodeAfter(_tail, newNode);
            return newNode;
        }

        /// <summary>
        /// 	Adds a new node containing the specified value before the specified existing node in the DoublyLinkedList.
        /// </summary>
        /// <returns> The new DoublyLinkedListNode containing value . </returns>
        /// <param name="node"> The DoublyLinkedListNode before which to insert a new DoublyLinkedListNode containing <paramref
        ///  	name="value" /> . </param>
        /// <param name="value"> The value to add to the DoublyLinkedList. </param>
        public DoublyLinkedListNode<T> AddBefore(DoublyLinkedListNode<T> node, T value)
        {
            ValidateNode(node);
            var newNode = DoublyLinkedListNode<T>.Allocate(node.List, value);
            InternalInsertNodeBefore(node, newNode);
            return newNode;
        }

        /// <summary>
        /// 	Adds a new node containing the specified value after the specified existing node in the DoublyLinkedList.
        /// </summary>
        /// <returns> The new DoublyLinkedListNode containing value . </returns>
        /// <param name="node"> The DoublyLinkedListNode after which to insert a new DoublyLinkedListNode containing <paramref
        ///  	name="value" /> . </param>
        /// <param name="value"> The value to add to the DoublyLinkedList. </param>
        public DoublyLinkedListNode<T> AddAfter(DoublyLinkedListNode<T> node, T value)
        {
            ValidateNode(node);
            var newNode = DoublyLinkedListNode<T>.Allocate(node.List, value);
            InternalInsertNodeAfter(node, newNode);
            return newNode;
        }

        #endregion

        #region Add Node

        /// <summary>
        /// 	Adds the specified new newNode at the start of the DoublyLinkedList.
        /// </summary>
        /// <param name="newNode"> The new DoublyLinkedListNode to add at the start of the DoublyLinkedList. </param>
        public void AddFirst(DoublyLinkedListNode<T> newNode)
        {
            ValidateNewNode(newNode);
            if (_head == null)
            {
                InternalInsertNodeToEmptyList(newNode);
            }
            else
            {
                InternalInsertNodeBefore(_head, newNode);
            }
            newNode.List = this;
        }

        /// <summary>
        /// 	Adds the specified new newNode at the end of the DoublyLinkedList.
        /// </summary>
        /// <param name="newNode"> The new DoublyLinkedListNode to add at the end of the DoublyLinkedList. </param>
        public void AddLast(DoublyLinkedListNode<T> newNode)
        {
            ValidateNewNode(newNode);
            if (_tail == null)
            {
                InternalInsertNodeToEmptyList(newNode);
            }
            else
            {
                InternalInsertNodeAfter(_tail, newNode);
            }
            newNode.List = this;
        }

        /// <summary>
        /// 	Adds the specified new node before the specified existing node in the DoublyLinkedList.
        /// </summary>
        /// <param name="node"> The DoublyLinkedListNode before which to insert newNode. </param>
        /// <param name="newNode"> The new DoublyLinkedListNode to add to the DoublyLinkedList. </param>
        public void AddBefore(DoublyLinkedListNode<T> node, DoublyLinkedListNode<T> newNode)
        {
            ValidateNode(node);
            ValidateNewNode(newNode);
            InternalInsertNodeBefore(node, newNode);
            newNode.List = this;
        }

        /// <summary>
        /// 	Adds the specified new node after the specified existing node in the DoublyLinkedList.
        /// </summary>
        /// <param name="node"> The DoublyLinkedListNode after which to insert newNode . </param>
        /// <param name="newNode"> The new DoublyLinkedListNode to add to the DoublyLinkedList. </param>
        public void AddAfter(DoublyLinkedListNode<T> node, DoublyLinkedListNode<T> newNode)
        {
            ValidateNode(node);
            ValidateNewNode(newNode);
            InternalInsertNodeAfter(node, newNode);
            newNode.List = this;
        }

        #endregion

        #region Internal Insert

        private void InternalInsertNodeToEmptyList(DoublyLinkedListNode<T> newNode)
        {
            newNode.Next = null;
            newNode.Previous = null;
            _head = newNode;
            _tail = newNode;
            _count++;
        }

        private void InternalInsertNodeBefore(DoublyLinkedListNode<T> node, DoublyLinkedListNode<T> newNode)
        {
            if (node == _head)
            {
                newNode.Next = node;
                newNode.Previous = null;
                node.Previous = newNode;
                _head = newNode;
            }
            else
            {
                newNode.Next = node;
                newNode.Previous = node.Previous;
                node.Previous.Next = newNode;
                node.Previous = newNode;
            }
            _count++;
        }

        private void InternalInsertNodeAfter(DoublyLinkedListNode<T> node, DoublyLinkedListNode<T> newNode)
        {
            if (node == _tail)
            {
                newNode.Next = null;
                newNode.Previous = node;
                node.Next = newNode;
                _tail = newNode;
            }
            else
            {
                newNode.Next = node.Next;
                newNode.Previous = node;
                node.Next = newNode;
                newNode.Next.Previous = newNode;
            }
            _count++;
        }

        #endregion

        #endregion

        #region Remove

        #region Remove Node

        /// <summary>
        /// 	Removes the node at the start of the DoublyLinkedList.
        /// </summary>
        public void RemoveFirst()
        {
            if (_head == null)
            {
                throw new InvalidOperationException(Resx.LinkedListEmpty);
            }
            InternalRemoveNode(_head);
        }

        /// <summary>
        /// 	Removes the node at the end of the DoublyLinkedList.
        /// </summary>
        public void RemoveLast()
        {
            if (_tail == null)
            {
                throw new InvalidOperationException(Resx.LinkedListEmpty);
            }
            InternalRemoveNode(_tail);
        }

        /// <summary>
        /// 	Removes the specified node from the DoublyLinkedList.
        /// </summary>
        /// <param name="node"> The DoublyLinkedListNode to remove from the DoublyLinkedList. </param>
        public void Remove(DoublyLinkedListNode<T> node)
        {
            ValidateNode(node);
            InternalRemoveNode(node);
        }

        #endregion

        #region Internal Remove

        internal void InternalRemoveNode(DoublyLinkedListNode<T> node)
        {
            if (node == _head || node == _tail)
            {
                if (node == _head)
                {
                    _head = node.Next;
                    if (_head != null)
                    {
                        _head.Previous = null;
                    }
                }
                if (node == _tail)
                {
                    _tail = node.Previous;
                    if (_tail != null)
                    {
                        _tail.Next = null;
                    }
                }
            }
            else
            {
                node.Next.Previous = node.Previous;
                node.Previous.Next = node.Next;
            }
            DoublyLinkedListNode<T>.Free(node);
            _count--;
        }

        #endregion

        #endregion

        #region Validate

        internal void ValidateNewNode(DoublyLinkedListNode<T> node)
        {
            if (node == null)
            {
                throw new ArgumentNullException("node");
            }
            if (node.List != null)
            {
                throw new InvalidOperationException(Resx.LinkedListNodeIsAttached);
            }
        }

        internal void ValidateNode(DoublyLinkedListNode<T> node)
        {
            if (node == null)
            {
                throw new ArgumentNullException("node");
            }
            if (node.List != this)
            {
                throw new InvalidOperationException(Resx.ExternalLinkedListNode);
            }
        }

        #endregion

        #region Nested Type Enumerator<T>

        /// <summary>
        /// 	Enumerates the elements of a DoublyLinkedList.
        /// </summary>
        [StructLayout(LayoutKind.Sequential)]
        public struct Enumerator : IEnumerator<T>
        {
            #region Fields & Properties

            private readonly DoublyLinkedList<T> _list;
            private DoublyLinkedListNode<T> _node;
            private T _current;
            private int _index;

            #endregion

            #region Constructors

            internal Enumerator(DoublyLinkedList<T> list)
            {
                _list = list;
                _index = 0;
                _current = default(T);
                _node = list._head;
            }

            #endregion

            #region Implementation of IDisposable

            /// <summary>
            /// 	Performs application-defined tasks associated with freeing, releasing, or resetting unmanaged resources.
            /// </summary>
            public void Dispose()
            {
            }

            #endregion

            #region Implementation of IEnumerator

            /// <summary>
            /// 	Advances the enumerator to the next element of the DoublyLinkedList.
            /// </summary>
            /// <returns> true if the enumerator was successfully advanced to the next element; false if the enumerator has passed the end of the collection. </returns>
            public bool MoveNext()
            {
                if (_node == null)
                {
                    _index = _list.Count + 1;
                    return false;
                }
                _index++;
                _current = _node.Value;
                _node = _node.Next;
                return true;
            }

            /// <summary>
            /// 	Sets the enumerator to its initial position, which is before the first element in the collection.
            /// </summary>
            void IEnumerator.Reset()
            {
                _index = 0;
                _current = default(T);
                _node = _list._head;
            }

            /// <summary>
            /// 	Gets the element in the collection at the current position of the enumerator.
            /// </summary>
            /// <returns> The element in the collection at the current position of the enumerator. </returns>
            public T Current
            {
                get
                {
                    return _current;
                }
            }

            /// <summary>
            /// 	Gets the current element in the collection.
            /// </summary>
            /// <returns> The current element in the collection. </returns>
            object IEnumerator.Current
            {
                get
                {
                    if (_index == 0 || _index == (_list.Count + 1))
                    {
                        throw new InvalidOperationException(Resx.EnumOperationCantHappen);
                    }
                    return _current;
                }
            }

            #endregion
        }

        #endregion
    }
}